/*
 * OK, it appears that what I've uploaded before
 * was a false heapsort.
 */
#include <stdio.h>
#ifdef DEBUG
#include <string.h>
#endif

#define NMAX 500000


/* Dear diary,
 * This function takes two ptrs to ints and swaps them around.
 */
void
swap_int(int* a, int* b)
{
	int T;
	T  = *a;
	*a = *b;
	*b =  T;
}



/* Dear diary,
 * This function creates a heap structure.
 */
void
Heap_sort__sift_down(int * array, int start, int end)
{
	int root = start,
	    child,
	    swap;

	while (root * 2 + 1 <= end) {
		child = root * 2 + 1;
		swap = root;

		/* These two conditials check whether we have
		 * a bigger number as a child. If so, we will
		 * swap them. */
		if (array[swap] < array[child])
			swap = child;

		if (child+1 <= end && array[swap] < array[child+1])
			swap = child+1;

		if (swap != root) {
			swap_int(&array[root], &array[swap]);
			root = swap;
		} else {
			return; /* children are less than their root */
		}
	}
}



void
Heap_sort__heapify(int* array, int size)
{
	int start = size / 2 - 1;

	while (start >= 0) {
		/* Building heap from the bottom */
		Heap_sort__sift_down(array, start--, size - 1);
	}
}



/* Dear diary,
 * This is the main logical 'body' of heap sort.
 * Firstly, we initialize the heap by adding elements
 * 	from array to heap and maintaining its integrity
 * 	(swapping elements in case of disorder).
 * After that maximum element will be array[0]. So we
 * 	swap it with array[size - 1] (last element) and
 * 	then fix the heap.
 * This is it.
 */
void
Heap_sort(int *array, int size)
{
	int end = size - 1;

	Heap_sort__heapify(array, size);

	while (end > 0) {
		swap_int(&array[end], &array[0]);

		Heap_sort__sift_down(array, 0, --end);
	}
}


/*             HEAP:
 *
 *    1|                        max[0]              :: Elements on N-th level are NOT
 *                            /     \                     sorted, but they are GUARANTEED
 *    2|               (max-1)[1]    (max-2)[2]           to be less than any of elem. on
 *                   /       \       /         \          (N-1) level and more than any of elem.
 *    3|    (max-3)[3] (max-4)[4] (max-5)[5] (max-6)[6]   on (N+1) level.
 *               /
 *    4|     (min)[7]
 */


int
main(void)
{
	int n, array[NMAX];
	register int i = 0;

	(void)freopen("heap.in", "rt", stdin);
	(void)freopen("heap.out", "w", stdout);
#ifdef DEBUG
	(void)memset(array, 0, sizeof(array));
#endif

	(void)scanf("%d\n", &n);
	while (i<n)
		(void)scanf("%d", &array[i++]);
	Heap_sort(array, n);
	i = 0;
	while (i<n)
		(void)printf("%d ", array[i++]);
	(void)putchar('\n');
	return 0;
}
